package day19;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/19 9:57
 */

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
 *
 * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
 * 输出：["eat","oath"]
 * 示例 2：
 *
 *
 * 输入：board = [["a","b"],["c","d"]], words = ["abcb"]
 * 输出：[]
 */
public class Solution3 {
    public List<String> findWords(char[][] board, String[] words) {
        int [][]d = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        Trie trie = new Trie();
        boolean [][]f = new boolean[board.length][board[0].length];
        trie.insert(words);
        Set<String> list = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                char aChar = board[i][j];
                backtracking(trie,list,d,String.valueOf(aChar),i,j,board,f);
            }
        }
        return new ArrayList<String>(list);
    }
    private void backtracking(Trie trie, Set<String> list, int[][] d, String str, int m, int n, char[][] board,boolean[][] f) {
        if(!trie.startsWith(str)){
            return;
        }
        f[m][n] = true;
        if(trie.search(str)){
            list.add(str);
        }
        for (int i = 0; i < 4; i++) {
            int w = d[i][0]+m;
            int l = d[i][1]+n;
            if(w>=0&&l>=0&&w<board.length&&l<board[0].length&&!f[w][l]){
                StringBuilder stringBuilder = new StringBuilder();
                stringBuilder.append(str);
                stringBuilder.append(board[w][l]);
                backtracking(trie,list,d,stringBuilder.toString(),w,l,board,f);
            }
        }
        f[m][n] = false;
    }
}
